package problem.array;

public class problem55 {

	static boolean flag = false;
	public static void main(String[] args) {
		int [] nums = {0};
		System.out.println(canJump(nums));
		System.err.println(canJump2(nums));
	}
	
	 public static boolean canJump(int[] nums) {
		 int len = nums.length;
		int [] step = new int[len];
		for(int i = 0;i < len;i++){
			step[i] = nums[i]+i;
		}
		int max = 0;
		for(int i = 0;i < nums.length;i++){
	
			if(step[i] > max ){
				max = step[i];
			}
			if(max >= len-1){
				return true;
			}
			if(nums[i] == 0){
				if(max == step[i]){
					return false;
				}
			}
		}
		if(max >= len-1){
			return true;
		}
		return false;
	 }
	 public static void dfsJum(int s,int []nums){
		 if(flag == true){
			 return;
		 }
		 if(s == nums.length-1){
			 flag = true;
		 }
		 if(nums[s] == 0){
			 return;
		 }
		 int x = nums[s];
		 
		 int i =1;
		 for(i = 1;i <= x && s+i < nums.length;i++){
			 dfsJum(s+i, nums);
		 }
		 if(s+i >= nums.length){
			flag = true;
			return ;
		 }
		 
	 } 
	 
	 public static boolean canJump2(int[] nums){
		 int step = 0;
		 int max= 0;
		 int len = nums.length-1;
		 for(int i= 0;i < nums.length;i++){
			 step = nums[i]+i;
			 if(step > max){
				 max = step;
			 }
			
			 if(max >= len){
				 return true;
			 }
			 if(nums[i] == 0 && max <= step){
				 return false;
			 }
		 }
		 if(max >= len){
			 return true;
		 }
		 return false;
	 }
}
